/*
 * @lc app=leetcode.cn id=2049 lang=typescript
 *
 * [2049] 统计最高分的节点数目
 */

// @lc code=start
function countHighestScoreNodes(parents: number[]): number {
  const n = parents.length;
  // 记录每个节点的子节点
  const children: number[][] = new Array(n).fill(0).map(() => []);
  for (let i = 0; i < n; i++) {
    const idx = parents[i];
    if (idx === -1) continue;
    children[idx].push(i);
  }
  // dfs搜索每个节点的最高分
  const dfs = (node: number): number => {
    // 当前节点的分数
    let score = 1;
    // 默认为当前节点的数量为1
    let sum = 1;
    // 深搜子节点
    for (const child of children[node]) {
      const cnt = dfs(child);
      score *= cnt;
      sum += cnt;
    }
    // 计算当前节点父节点及父节点另一半子树
    if (node !== 0) {
      score *= n - sum;
    }
    // 计算最高分的数量
    if (maxScore === score) {
      ans++;
    } else if (score > maxScore) {
      maxScore = score;
      ans = 1;
    }
    // 返回当前节点和它的子节点的数量
    return sum;
  };

  let ans = 0;
  let maxScore = 0;

  dfs(0);
  return ans;
}
// @lc code=end
